/**
 * 
 */
package linkedlist.passed;

/**
 * @author xyyi
 *
 */
public class RemoveNthNodeFromEndofList {

	/**
	Given a linked list, remove the nth node from the end of list and return its head.

			For example,

			   Given linked list: 1->2->3->4->5, and n = 2.

			   After removing the second node from the end, the linked list becomes 1->2->3->5.	
	*/

	/* Definition for singly-linked list.*/
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}

	/**
	 * 
	 */
	public ListNode removeNthFromEnd(ListNode head, int n) {
		if (head == null)
			return head;

		ListNode extraHead = new ListNode(-1);
		extraHead.next = head;

		ListNode fast = extraHead;
		ListNode slow = extraHead;
		for (int i = 0; i <= n; i++) {
			fast = fast.next;
		}

		while (fast != null) {
			fast = fast.next;
			slow = slow.next;
		}

		slow.next = slow.next.next;

		return extraHead.next;
	}

	/**
	 * 
	 */
	public RemoveNthNodeFromEndofList() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
